Search results for "Structural complexity"
showing 10 items of 12 documents
Mixed valence mono- and hetero-metallic grid catenanes
2015
Multicomponent self-assembly was employed to obtain, in the solid state, a series of mixed valence mono- and hetero-metallic grid catenanes, which were characterized by single crystal X-ray diffraction.
Algorithmic Information Theory and Computational Complexity
2013
We present examples where theorems on complexity of computation are proved using methods in algorithmic information theory. The first example is a non-effective construction of a language for which the size of any deterministic finite automaton exceeds the size of a probabilistic finite automaton with a bounded error exponentially. The second example refers to frequency computation. Frequency computation was introduced by Rose and McNaughton in early sixties and developed by Trakhtenbrot, Kinber, Degtev, Wechsung, Hinrichs and others. A transducer is a finite-state automaton with an input and an output. We consider the possibilities of probabilistic and frequency transducers and prove sever…
On Physical Problems that are Slightly More Difficult than QMA
2013
We study the complexity of computational problems from quantum physics. Typically, they are studied using the complexity class QMA (quantum counterpart of NP) but some natural computational problems appear to be slightly harder than QMA. We introduce new complexity classes consisting of problems that are solvable with a small number of queries to a QMA oracle and use these complexity classes to quantify the complexity of several natural computational problems (for example, the complexity of estimating the spectral gap of a Hamiltonian).
Contrasting structural complexity differentiate hunting strategy in an ambush apex predator.
2021
AbstractStructural complexity is known to influence prey behaviour, mortality and population structure, but the effects on predators have received less attention. We tested whether contrasting structural complexity in two newly colonised lakes (low structural complexity lake—LSC; high structural complexity—HSC) was associated with contrasting behaviour in an aquatic apex predator, Northern pike (Esox lucius; hereafter pike) present in the lakes. Behaviour of pike was studied with whole-lake acoustic telemetry tracking, supplemented by stable isotope analysis of pike prey utilization and survey fishing data on the prey fish community. Pike displayed increased activity, space use, individual …
Complexity and interaction: comparing the development of L1 and L2
2011
In research into first and second language development, the focus has mainly been either on the formal features of learner language alone (both L1 and L2) or on the interaction between learners and their caretakers (L1) or native speaker peers (L2).These research traditions have been kept a part even though it has been widely acknowledged that both first and second languages are appropriated essentially in social interaction. This paper aims to strengthen the connection between social and formal approaches by combining interactional views with those focusing on the structural complexity of learner language. Some excerpts from L1 and L2 interaction data (in the Finnish language) are discusse…
MLU and IPSyn measuring absolute complexity
2009
This article compares the results of Mean Length of Utterance (MLU) and Index of Productive Syntax (IPSyn) with the structural complexity of spontaneous utterances produced by 30-month-old Finnish children in a semi-structured playing situation. The comparison was carried out in order to determine the aspects of structural complexity which can be detected with MLU and IPSyn. This research adopts the frameworks of absolute complexity together with a multidimensional view of utterance structure and, furthermore, applies it through Utterance Analysis (UA). The results of the comparison between the metrics and changes in structural complexity discovered by UA reveal that MLU and IPSyn do functi…
Effects of Kolmogorov complexity present in inductive inference as well
1997
For all complexity measures in Kolmogorov complexity the effect discovered by P. Martin-Lof holds. For every infinite binary sequence there is a wide gap between the supremum and the infimum of the complexity of initial fragments of the sequence. It is assumed that that this inevitable gap is characteristic of Kolmogorov complexity, and it is caused by the highly abstract nature of the unrestricted Kolmogorov complexity.
Inductive inference of recursive functions: Complexity bounds
2005
This survey includes principal results on complexity of inductive inference for recursively enumerable classes of total recursive functions. Inductive inference is a process to find an algorithm from sample computations. In the case when the given class of functions is recursively enumerable it is easy to define a natural complexity measure for the inductive inference, namely, the worst-case mindchange number for the first n functions in the given class. Surely, the complexity depends not only on the class, but also on the numbering, i.e. which function is the first, which one is the second, etc. It turns out that, if the result of inference is Goedel number, then complexity of inference ma…
Non-intersecting Complexity
2006
A new complexity measure for Boolean functions is introduced in this article. It has a link to the query algorithms: it stands between both polynomial degree and non-deterministic complexity on one hand and still is a lower bound for deterministic complexity. Some inequalities and counterexamples are presented and usage in symmetrisation polynomials is considered.
Effects of structural complexity on epifaunal assemblages associated with two intertidal Mediterranean seaweeds
2023
Brown foundation seaweeds are key elements increasing substrate heterogeneity and shaping the biodiversity in rocky coastal ecosystems. They are, however, vulnerable species that are declining due to multiple anthropogenic and climate change stressors, leading to a shift to less structural complex habitats. We investigate the role of structural attributes of two intertidal macroalgae, Ericaria amentacea and Laurencia obtusa, in shaping the abundance and diversity of their associated epifaunal assemblages. For this aim, we measured seaweeds’ biomass, thallus volume and length (used here as proxy of substrate complexity), and explored which seaweeds’ substrate attribute explained better varia…